package com.zbcn.algorithm;

import com.google.common.collect.Lists;
import lombok.Data;

import java.util.Collections;
import java.util.List;

/**
 * 贪心算法:
 * 假设有n 个区间，分别是[l1,r1],[l2,r2],[l3,r3],......[ln,rn]. 从这 n 个区间中选出 某些区间，要求这些区间满足两两不相交【端点相交的情况不算相交】，最多能选出多少个区间呢？
 */
@Data
public class T22_Greedy {


    /**
     * 1. n 个区间，最左侧的 l min ，最右侧的 端点 是 rmax。 最终是要选取几个区间，在 l min  --- r max  区间内覆盖
     * 2. 将 几个区间按照 有端点 right 从小到 大 排序
     * 3. 每次选择左侧的端点与已经覆盖的区间不重合，而且右侧端点尽量小的区间，这样让剩下的未付盖区间尽量大，以容纳更多区间
     * @param intervals
     * @return
     */
    public List<Interval> findMaxNumIntervals(List<Interval> intervals){

        List<Interval> result = Lists.newArrayList();
        // 将集合 按照 right 边界 从小到大排序， 区间最小的就在最前面了
        Collections.sort(intervals);
        // 已经覆盖的右侧端点
        int coveredIntervalRight = 0;
        for (int i= 0; i < intervals.size(); i++){
            Interval interval = intervals.get(i);
            if (coveredIntervalRight <= interval.left){
                result.add(interval);
                coveredIntervalRight = interval.right;
            }
        }
        return result;
    }


    public static class Interval implements Comparable<Interval>{

        private int left;

        private int right;

        public Interval() {
        }

        public Interval(int left, int right) {
            this.left = left;
            this.right = right;
        }

        @Override
        public int compareTo(Interval o) {
            return this.right - o.right;
        }
    }

}
